//
// Created by ASUS on 2023/9/21.
//
#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;


int fast_pow(int a,int b){
	a%=mod;
	int ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}